package NO6_Tree;

/**
 * 2025-8-18
 * 力扣 - 530. 二叉搜索树的最小绝对差
 * <p>
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 差值是一个正数，其数值等于两值之差的绝对值。
 */
public class GetMinimumDifferenceMain {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                4,
                new TreeNode(2, new TreeNode(1), new TreeNode(3)),
                new TreeNode(6));
        TreeNode root2 = new TreeNode(
                5,
                new TreeNode(4),
                new TreeNode(7));
        System.out.println(getMinimumDifference(root));
        System.out.println("---------------------");
        System.out.println(getMinimumDifference(root2));
    }


    // BFS
//    public static int getMinimumDifference(TreeNode root){
//        if (root == null) {
//            return 0;
//        }
//
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//
//        List<Integer> treeDataList = new ArrayList<>();
//        while (!queue.isEmpty()) {
//            int levelSize = queue.size();
//            for (int i = 0; i < levelSize; i++) {
//                TreeNode node = queue.poll();
//                treeDataList.add(node.val);
//
//                if (node.left != null) {
//                    queue.offer(node.left);
//                }
//                if (node.right != null) {
//                    queue.offer(node.right);
//                }
//            }
//        }
//        // 将树整理成数组
//        // 排序
//        Collections.sort(treeDataList);
//        // 排序后最小值为相邻两数的差
//        int min = Integer.MAX_VALUE;
//        for (int i = 1; i < treeDataList.size(); i++){
//            min = Math.min(min, Math.abs(treeDataList.get(i) - treeDataList.get(i - 1)));
//        }
//        return min;
//    }

    // DFS - 利用中序遍历之后的特性 -> 升序数组；最小值=相邻两数的差
    // 这里提交的时候不要带 static ，因为他会多次调用这个方法，使用 static 会保留之前的值
    private static Integer prev = null;
    private static int minDiff = Integer.MAX_VALUE;

    public static int getMinimumDifference(TreeNode root){
        inorder(root);
        return minDiff;
    }

    private static void inorder(TreeNode node) {
        if (node == null){
            return;
        }

        inorder(node.left);

        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;

        inorder(node.right);
    }
}
